package com.algrithom.unionfind;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 187. 重复的DNA序列
 * 
 * @author think
 */
public class Solution7 {
    
    public static void main(String[] args){
        Solution7 solution7 = new Solution7();
        System.out.println(solution7.findRepeatedDnaSequences1("AAAAAAAAAAAAA"));
    }
    
    public List<String> findRepeatedDnaSequences1(String s){
        List<String> ans = new ArrayList<>();
        Map<String,Integer> cnt = new HashMap<>();
        int n = s.length();
        for (int i = 0; i <= n - 10; ++i) {
            String sub = s.substring(i,i + 10);
            cnt.put(sub,cnt.getOrDefault(sub,0) + 1);
            if (cnt.get(sub) == 2) {
                ans.add(sub);
            }
        }
        return ans;
    }
    
    public List<String> findRepeatedDnaSequences2(String s){
        List<String> ans = new ArrayList<>();
        int n = s.length();
        Map<String,Integer> map = new HashMap<>();
        for (int i = 0; i + 10 <= n; i++) {
            String cur = s.substring(i,i + 10);
            int cnt = map.getOrDefault(cur,0);
            if (cnt == 1) {
                ans.add(cur);
            }
            map.put(cur,cnt + 1);
        }
        return ans;
    }
}